package kyssion.leetcode.num1_50;

/**
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 */
public class code4_寻找两个有序数组的中位数 {
    public static void main(String[] args) {
        System.out.println(new code4_寻找两个有序数组的中位数().findMedianSortedArrays(
                new int[]{1}, new int[]{2, 3, 4, 5, 6}
        ));
        System.out.println(new code4_寻找两个有序数组的中位数().findMedianSortedArrays(
                new int[]{3}, new int[]{1, 2, 4, 5, 6}
        ));
        System.out.println(new code4_寻找两个有序数组的中位数().findMedianSortedArrays2(
                new int[]{16, 45, 52, 74, 93, 102, 251, 274, 341, 392, 415, 490, 502, 528, 530, 633, 772, 773, 836, 853, 858, 999, 1014, 1034, 1116, 1169, 1217, 1291, 1349, 1397, 1455, 1458, 1462, 1495, 1518, 1561, 1576, 1613, 1667, 1767, 1776, 1832, 1892, 1960, 2016, 2079, 2107, 2126, 2220, 2324, 2338, 2372, 2426, 2558, 2563, 2587, 2705, 2713, 2721, 2758, 2766, 2859, 2872, 2936, 3053, 3086, 3116, 3158, 3160, 3179, 3245, 3280, 3291, 3337, 3462, 3586, 3593, 3623, 3632, 3635, 3698, 3716, 3906, 3952, 3981, 4005, 4021, 4031, 4051, 4096, 4102, 4103, 4166, 4195, 4230, 4240, 4283, 4294, 4432, 4433, 4520, 4555, 4583, 4603, 4629, 4632, 4635, 4714, 4729, 4788, 4889, 4944, 4959, 4962, 4999, 5020, 5035, 5053, 5080, 5104, 5114, 5125, 5135, 5144, 5184, 5287, 5290, 5293, 5302, 5329, 5366, 5398, 5435, 5454, 5546, 5618, 5661, 5675, 5807, 5824, 5852, 5871, 5887, 5894, 5926, 5977, 6000, 6112, 6131, 6149, 6161, 6178, 6243, 6385, 6427, 6450, 6469, 6527, 6552, 6588, 6694, 6700, 6761, 6767, 6791, 6921, 6926, 6964, 7027, 7113, 7132, 7132, 7175, 7183, 7231, 7309, 7316, 7337, 7376, 7411, 7451, 7454, 7522, 7634, 7635, 7667, 7704, 7743, 7744, 7803, 8028, 8082, 8119, 8165, 8189, 8238, 8239, 8265, 8333, 8352, 8463, 8566, 8583, 8640, 8706, 8793, 8827, 8834, 8860, 9035, 9037, 9120, 9129, 9164, 9271, 9304, 9309, 9309, 9312, 9326, 9363, 9480, 9493, 9512, 9560, 9685, 9737, 9754, 9905, 10040, 10049, 10078, 10116, 10206, 10252, 10260, 10351, 10397, 10482, 10510, 10572, 10602, 10606, 10677, 10698, 10720, 10732, 10797, 10826, 10900, 10937, 10939, 10954, 10955, 11001, 11013, 11122, 11125, 11167, 11241, 11242, 11254, 11269, 11276, 11313, 11333, 11353, 11356, 11356, 11515, 11585, 11769, 11791, 11795, 11918, 11988, 12031, 12100, 12110, 12183, 12203, 12281, 12301, 12330, 12401, 12417, 12432, 12461, 12480, 12520, 12522, 12703, 12723, 12768, 12893, 12972, 12975, 13000, 13022, 13119, 13178, 13241, 13297, 13330, 13339, 13365, 13449, 13457, 13468, 13498, 13502, 13549, 13589, 13625, 13674, 13850, 13905, 13910, 13957, 13964, 13995, 14127, 14204, 14212, 14213, 14344, 14357, 14362, 14376, 14395, 14400, 14413, 14445, 14521, 14615, 14646, 14672, 14673, 14683, 14749, 14772, 14777, 14780, 14789, 14891, 14945, 14975, 14986, 15005, 15030, 15084, 15097, 15107, 15195, 15260, 15266, 15372, 15377, 15415, 15431, 15486, 15539, 15581, 15659, 15705, 15803, 15850, 15858, 15952, 15989, 16107, 16385, 16450, 16451, 16517, 16566, 16669, 16703, 16710, 16839, 16874, 16903, 16903, 16908, 16959, 16982, 16994, 16999, 17030, 17036, 17175, 17193, 17203, 17214, 17222, 17313, 17313, 17366, 17429, 17453, 17510, 17532, 17709, 17772, 17836, 17838, 17874, 17930, 17969, 17996, 17996, 18051, 18061, 18083, 18154, 18158, 18167, 18167, 18175, 18203, 18238, 18325, 18380, 18435, 18445, 18454, 18497, 18656, 18685, 18710, 18723, 18730, 18740, 18750, 18803, 18809, 18845, 18882, 18966, 19032, 19040, 19084, 19157, 19287, 19327, 19343, 19372, 19378, 19420, 19494, 19579, 19611, 19625, 19628, 19641, 19679, 19685, 19758, 19808, 19811, 19869, 20089, 20112, 20316, 20317, 20332, 20376, 20392, 20398, 20405, 20443, 20536, 20545, 20611, 20718, 20726, 20735, 20743, 20839, 20903, 20935, 20945, 20961, 20962, 20998, 21009, 21162, 21174, 21174, 21216, 21222, 21271, 21329, 21384, 21483, 21555, 21590, 21618, 21618, 21768, 21776, 21788, 21858, 21860, 21876, 21877, 21884, 21951, 21986, 22126, 22137, 22197, 22213, 22249, 22268, 22308, 22377, 22513, 22541, 22607, 22627, 22630, 22644, 22790, 22800, 22825, 22921, 22959, 22973, 22991, 23014, 23115, 23151, 23170, 23219, 23273, 23364, 23412, 23528, 23542, 23602, 23607, 23660, 23674, 23709, 23725, 23739, 23773, 23775, 23847, 23914, 23916, 23929, 23949, 23999, 24021, 24102, 24257, 24271, 24319, 24413, 24599, 24606, 24627, 24702, 24804, 24881, 24904, 24907, 24914, 24921, 24932, 25133, 25168, 25260, 25270, 25384, 25450, 25549, 25641, 25644, 25646, 25660, 25683, 25685, 25760, 25773, 25833, 25864, 25926, 25953, 25956, 26031, 26052, 26055, 26095, 26105, 26133, 26171, 26180, 26209, 26222, 26243, 26267, 26286, 26302, 26356, 26411, 26486, 26623, 26675, 26763, 26800, 26801, 26856, 26972, 27002, 27032, 27286, 27320, 27326, 27339, 27346, 27347, 27394, 27409, 27419, 27425, 27547, 27621, 27671, 27735, 27741, 27767, 27770, 27787, 27834, 27852, 27852, 27909, 27922, 27939, 27998, 28012, 28038, 28120, 28200, 28222, 28245, 28253, 28261, 28360, 28399, 28481, 28627, 28703, 28732, 28761, 28803, 28803, 28824, 28907, 28945, 28957, 28985, 29122, 29244, 29249, 29338, 29358, 29376, 29447, 29544, 29546, 29599, 29614, 29627, 29670, 29684, 29710, 29772, 29801, 29814, 29844, 29934, 29949, 29991, 30033, 30096, 30235, 30242, 30351, 30493, 30509, 30574, 30575, 30583, 30656, 30817, 30849, 30864, 30878, 30885, 30890, 30893, 30933, 30936, 30969, 30988, 31004, 31094, 31140, 31176, 31230, 31241, 31242, 31250, 31268, 31272, 31423, 31509, 31567, 31678, 31709, 31717, 31902, 31977, 31989, 32000, 32043, 32106, 32138, 32198, 32214, 32305, 32402, 32421, 32482, 32554, 32561, 32573, 32672, 32747}
                , new int[]{512, 757, 843, 870, 1037, 1464, 1868, 1955, 1968, 2091, 2249, 2553, 2607, 2644, 2836, 2936, 3226, 3378, 3639, 3743, 3874, 3998, 4091, 4304, 4401, 4732, 5224, 5443, 5659, 6108, 6730, 6996, 7636, 7849, 7990, 8188, 8194, 8532, 9103, 9131, 9148, 9207, 9483, 9555, 9648, 9856, 10390, 10789, 10801, 11005, 11024, 11571, 11615, 12250, 12285, 12834, 13025, 13346, 13549, 13616, 13758, 13760, 14156, 14173, 14414, 14475, 14562, 14842, 15062, 15125, 15212, 15235, 15369, 15551, 15646, 15756, 15998, 16082, 16225, 16434, 17026, 17317, 17893, 18249, 18353, 18600, 19505, 20080, 20272, 20834, 21596, 21701, 21758, 21768, 22271, 22314, 22341, 22785, 22790, 22927, 22934, 23182, 23406, 23478, 23493, 23909, 24093, 24342, 24670, 24680, 25708, 25904, 25974, 25993, 26023, 26326, 26753, 26867, 27001, 27082, 27231, 27353, 27484, 27886, 28150, 28317, 28623, 28666, 28679, 29147, 29196, 29246, 29361, 29635, 29763, 29821, 30176, 30294, 30296, 30481, 30609, 31093, 31099, 31281, 31634, 31830, 31975, 32047, 32071, 32100, 32297, 32753}
        ));
    }

    /**
     * 解法一 注意中位数的特性, 进行假设 生成数组A,B,划分成如下的部分
     * 想比较前面的方法特殊使用了中位这个概念
     * 将 text{left_A}left_A 和 text{left_B}left_B 放入一个集合，并将 text{right_A}right_A 和 text{right\_B}right_B 放入另一个集合。 再把这两个新的集合分别命名为 \text{left\_part}left_part 和 \text{right\_part}right_part：
     * <p>
     * left_part          |        right_part
     * A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
     * B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
     * 此时中位数就是
     * max(A[i−1],B[j−1]), 当 m + nm+n 为奇数时
     * (max(A[i−1],B[j−1])+min(A[i],B[j]))/2  当 m + nm+n 为偶数时
     * <p>
     * 这题很巧妙--> 假设a的中间就是中位数,那么b 对应的位置
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //保证中位数之前的值会在nums1中存在
        if (nums1.length > nums2.length || (nums1.length == nums2.length && nums1[0] > nums2[0])) {
            int[] item = nums1;
            nums1 = nums2;
            nums2 = item;
        }

        int index = nums1.length + nums2.length;
        int needBefore = index / 2;
        int lBefore = nums1.length;
        int sBefore = needBefore - lBefore;

        while (true) {
            int nowL = lBefore < nums1.length ? nums1[lBefore] : Integer.MAX_VALUE;
            int nowS = sBefore < nums2.length ? nums2[sBefore] : Integer.MAX_VALUE;
            int beforel = lBefore - 1 < 0 ? Integer.MIN_VALUE : nums1[lBefore - 1];
            int befores = sBefore - 1 < 0 ? Integer.MIN_VALUE : nums2[sBefore - 1];
            if (beforel > befores && beforel <= nowS) {
                if (index % 2 == 0) {
                    return ((double) beforel + (double) Math.min(nowS, nowL)) / 2;
                } else {
                    return Math.min(nowS, nowL);
                }
            } else if (beforel > befores && beforel > nowS) {
                lBefore = lBefore / 2;
                sBefore = needBefore - lBefore;
                continue;
            }
            if (befores > beforel && befores <= nowL) {
                if (index % 2 == 0) {
                    return ((double) befores + (double) Math.min(nowS, nowL)) / 2;
                } else {
                    return Math.min(nowS, nowL);
                }
            } else if (befores > beforel && befores > nowL) {
                //TODO 这里不知道怎么优化了,只能往上累加了
                lBefore += 1;
                sBefore = needBefore - lBefore;
//                sBefore = sBefore / 2;
//                lBefore = needBefore - sBefore;
                continue;
            }
            if (beforel == befores) {
                if (index % 2 == 0) {
                    return ((double) beforel + (double) (Math.min(nowS, nowL))) / 2;
                } else {
                    return Math.min(nowS, nowL);
                }
            }
        }
    }

    /**
     * 解法二 队列解法
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int nums2length = nums2.length;
        int[] r = new int[nums1.length + nums2length];

        int index = 0;
        int j = 0;
        for (int num : nums1) {
            while (j < nums2length && num > nums2[j]) {
                r[index] = nums2[j];
                j++;
                index++;
            }
            r[index] = num;
            index++;
        }
        for (; j < nums2length; j++) {
            r[index] = nums2[j];
            index++;
        }

        int mi = r.length / 2;
        return r.length % 2 == 1 ? r[mi] : (r[mi - 1] + r[mi]) / 2.0;
    }

    /**
     * 解法三 双向逼近,左边最大值和右边最小值
     *
     * @param A
     * @param B
     * @return
     */
    public double findMedianSortedArrays3(int[] A, int B[]) {
        int m = A.length;
        int n = B.length;
        if (m > n) {//保证m<n 意思就是B的长度大于等于A的长度
            int[] temp = A;
            A = B;
            B = temp;
            int tmp = m;
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (n + m + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j - 1] > A[i]) {
                iMin = iMin + 1;
            } else if (i > iMin && A[i - 1] > B[j]) {
                iMax = iMax - 1;
            } else {
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - 1];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }
                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(B[j], A[i]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }

    /**
     * 解法4 双层二分查找,查找nums1中的一个数组在num2中的位置,如果是中位数的位置,就成功
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays4 (int[] nums1, int[] nums2) {
        if (nums1.length == 0) {
            return getzhong(nums2);
        }
        if (nums2.length == 0) {
            return getzhong(nums1);
        }
        if (nums1.length == 1 && nums2.length == 1) {
            return ((double) nums1[0] + (double) nums2[0]) / 2.0;
        }
        int index = 0;
        int end = 2;
        int[][] need = new int[][]{
                {(nums1.length + nums2.length) / 2 + 1, -1},
                {(nums1.length + nums2.length) % 2 == 0 ?
                        (nums1.length + nums2.length) / 2 :
                        (nums1.length + nums2.length) / 2 + 1, -1}
        };
        while (index < end) {
            int ns1 = 0, ne1 = nums1.length - 1;
            int ns2 = 0, ne2 = nums2.length - 1;
            while (true) {
                int needone = nums1[(ns1 + ne1) / 2];
                int needtwo = nums2[(ns2 + ne2) / 2];
                int indexone = getAllIndex(nums2, (ns1 + ne1) / 2, needone, ns2, ne2, 1);
                int indextwo = getAllIndex(nums1, (ns2 + ne2) / 2, needtwo, ns1, ne1, 2);
                if (indexone > need[index][0]) {
                    ne1 = ((ns1 + ne1) / 2 - 1) < ns1 ? ns1 : (ns1 + ne1) / 2 - 1;
                } else if (indexone < need[index][0]) {
                    ns1 = ((ns1 + ne1) / 2 + 1) > ne1 ? ne1 : (ns1 + ne1) / 2 + 1;
                } else {
                    need[index][1] = needone;
                    break;
                }
                if (indextwo > need[index][0]) {
                    ne2 = ((ns2 + ne2) / 2 - 1) < ns2 ? ns2 : (ns2 + ne2) / 2 - 1;
                } else if (indextwo < need[index][0]) {
                    ns2 = ((ns2 + ne2) / 2 + 1) > ne2 ? ne2 : (ns2 + ne2) / 2 + 1;
                } else {
                    need[index][1] = needtwo;
                    break;
                }
            }
            index++;
        }
        return ((double) need[0][1] + (double) need[1][1]) / 2;
    }

    private double getzhong(int[] nums1) {
        if (nums1.length % 2 == 0) {
            return ((double) nums1[(nums1.length / 2 - 1)] + (double) nums1[(nums1.length / 2)]) / 2.0;
        } else {
            return nums1[nums1.length / 2];
        }
    }

    public int getAllIndex(int[] n, int before, int item, int start, int end, int type) {
        while (start < end) {
            if (type == 1) {
                if (item > n[(start + end) / 2]) {
                    start = (start + end) / 2 + 1;
                } else {
                    end = (start + end) / 2 - 1;
                }
            }else{
                if (item >= n[(start + end) / 2]) {
                    start = (start + end) / 2 + 1;
                } else {
                    end = (start + end) / 2 - 1;
                }
            }
        }
        if (n[start] < item) {
            return before + start + 2;
        } else {
            return before + start + 1;
        }
    }
}
